﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace GraphLibrary
{
    public abstract class Graph<TVertex, TEdge> : IGraph<TVertex, TEdge>
        where TEdge : IEdge<TVertex>
    {
        //ребра, исходящие из данной вершины
        private Dictionary<TVertex, List<TEdge>> _vertexOutEdges = new Dictionary<TVertex, List<TEdge>>();

        public IEnumerable<TVertex> Vertices
        {
            get
            {
                return _vertexOutEdges.Keys.ToList().AsReadOnly();
            }
        }

        public int CountOfVertices
        {
            get
            {
                return _vertexOutEdges.Count;
            }
        }

        public virtual IEnumerable<TVertex> AdjacentVertices(TVertex vertex)
        {
            if (ContainsVertex(vertex))
            {
                List<TVertex> adjacentVertices = new List<TVertex>();
                foreach (TEdge edge in _vertexOutEdges[vertex])
                {
                    adjacentVertices.Add(edge.Destination);
                }
                return adjacentVertices.AsReadOnly();
            }
            else
                throw new GraphException("There is no such vertex in the graph");
        }

        public virtual IEnumerable<TEdge> IncidentEdges(TVertex vertex)
        {
            return _vertexOutEdges[vertex];
        }

        public virtual void AddVertex(TVertex vertex)
        {
            if (!_vertexOutEdges.Keys.Contains(vertex))
            {
                _vertexOutEdges.Add(vertex, new List<TEdge>());
            }
            else
                throw new GraphException("This vertex is already in the graph");
        }

        public virtual void AddVertices(IEnumerable<TVertex> vertices)
        {
            List<TVertex> list = vertices.ToList();
            foreach (TVertex vertex in vertices)
            {
                if (_vertexOutEdges.Keys.Contains(vertex)) 
                    throw new GraphException("One of vertices is already in the graph");
                if ((list.FindAll(v => v.Equals(vertex)).Count > 1))
                    throw new GraphException("Duplicate vertices in the list");
            }
            foreach (TVertex vertex in vertices)
            {
                _vertexOutEdges.Add(vertex, new List<TEdge>());
            }
        }

        public virtual void AddEdge(TEdge edge)
        {
            CheckEdge(edge);
            _vertexOutEdges[edge.Source].Add(edge);
        }

        public virtual void AddEdges(IEnumerable<TEdge> edges)
        {
            List<TEdge> list = edges.ToList();
            foreach (TEdge edge in edges)
            {
                CheckEdge(edge);
                if (list.FindAll(e => e.Equals(edge)).Count > 1)
                    throw new GraphException("Duplicate edges in the list");
            }
            foreach (TEdge edge in edges)
            {
                _vertexOutEdges[edge.Source].Add(edge);
            }
        }

        private void CheckEdge(TEdge edge)
        {
            if (!_vertexOutEdges.ContainsKey(edge.Source) || !_vertexOutEdges.ContainsKey(edge.Destination))
                throw new GraphException("There is not such vertex");
            if (edge.Source.Equals(edge.Destination))
                throw new GraphException("Loops are not provided");
            if (ContainsEdge(edge.Source, edge.Destination))
                throw new GraphException("Duplicate edge is already in graph");
        }

        // удаление вершины и всех связанных с ней ребер
        protected virtual void RmVertex(TVertex vertex) 
        {
            _vertexOutEdges.Remove(vertex);
            foreach (TVertex v in _vertexOutEdges.Keys)
            {
                foreach (TEdge edge in _vertexOutEdges[v])
                {
                    if (edge.Destination.Equals(vertex))
                    {
                        _vertexOutEdges[v].Remove(edge);
                        break;
                    }
                }
            }       
        }

        public void RemoveVertex(TVertex vertex)
        {
            if (_vertexOutEdges.Keys.Contains(vertex))
                RmVertex(vertex);
            else
                throw new GraphException("The graph doesn't contains this vertex");
        }

        protected virtual bool RmEdge(TVertex source, TVertex destination)
        {
            foreach (TEdge edge in _vertexOutEdges[source])
            {
                if (edge.Destination.Equals(destination))
                {
                    _vertexOutEdges[source].Remove(edge);
                    return true;
                }
            }
            return false;
        }

        public virtual void RemoveVertices(IEnumerable<TVertex> vertices)
        {
            List<TVertex> list = vertices.ToList();
            foreach (TVertex vertex in vertices)
            {
                if (!ContainsVertex(vertex))
                    throw new GraphException("The graph doesn't contains one of edges.");
                if ((list.FindAll(v => v.Equals(vertex)).Count > 1))
                    throw new GraphException("Duplicate vertices in the list");
            }
            foreach (TVertex vertex in vertices)
            {
                RmVertex(vertex);
            }
        }

        public virtual void RemoveEdge(TEdge edge)
        {
            if (ContainsEdge(edge))
            {
                _vertexOutEdges[edge.Source].Remove(edge);
            }
            else
            {
                throw new GraphException("The graph doesn't contains this edge");
            }
        }

        public virtual void RemoveEdge(TVertex source, TVertex destination)
        {
            if (ContainsEdge(source, destination))
            {
                foreach (TEdge edge in _vertexOutEdges[source])
                {
                    if (edge.Destination.Equals(destination))
                    {
                        _vertexOutEdges[source].Remove(edge);
                        break;
                    }
                }
            }
            else
            {
                throw new GraphException("Graph doesn't contains this edge");
            }
        }

        public virtual void RemoveEdges(IEnumerable<TEdge> edges)
        {
            List<TEdge> list = edges.ToList();
            foreach (TEdge edge in edges)
            {
                if (!ContainsEdge(edge))
                    throw new GraphException("Graph doesn't contain one of vertices");
                if (list.FindAll(e => e.Equals(edge)).Count > 1)
                    throw new GraphException("Duplicate vertices in the list");
            }
            foreach (TEdge edge in edges)
            {
                _vertexOutEdges[edge.Source].Remove(edge);
            }
        }

        public bool ContainsVertex(TVertex vertex)
        {
            return _vertexOutEdges.ContainsKey(vertex);
        }

        public virtual bool ContainsEdge(TEdge edge)
        {
            if (_vertexOutEdges.ContainsKey(edge.Source))
                if (_vertexOutEdges[edge.Source].Contains(edge))
                    return true;
            return false;
        }

        public virtual bool ContainsEdge(TVertex source, TVertex destination)
        {
            if (_vertexOutEdges.ContainsKey(source))
                if (_vertexOutEdges[source].Find(e => e.Destination.Equals(destination)) != null)
                    return true;
            return false;
        }

        public virtual double[,] ToAgencyMatrix(Func<TEdge, double> weight)
        {
            int n = _vertexOutEdges.Count;
            double[,] matrix = new double[n, n];
            List<TVertex> vertices = Vertices.ToList();
            if (weight == null)
            {
                weight = e => 1;
            }
            for (int i = 0; i < n; i++)
            {
                foreach (TEdge edge in _vertexOutEdges[vertices[i]])
                {
                    matrix[i, vertices.IndexOf(edge.Destination)] = weight(edge);
                }
            }
            return matrix;
        }
    }
}